/*

Libreria

*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <glpk.h>
#include "ourlib.h"



void itoa(int n, char s[]){
	int i, sign;
	
	if ((sign = n) < 0)	/* record sign */
	n = -n;			/* make n positive */
	i = 0;
	do {			/* generate digits in reverse order */
		s[i++] = n % 10 + '0';	/* get next digit */
	} while ((n /= 10) > 0);	/* delete it */
	if (sign < 0)
		s[i++] = '-';
	s[i] = '\0';
	reverse(s);	
}

void reverse(char s[]){
	int i, j;
	char c;

	for (i = 0, j = strlen(s)-1; i<j; i++, j--) {
		c = s[i];
		s[i] = s[j];
		s[j] = c;
	}
}

void randomize(){
	srand(time(NULL));
	return;
}

int randomf(int min,int max){
	return min + (rand()%(max+1-min));
}

int exists_arc(glp_graph *G, int i, int j){   // G grafo da controllare, i coda, j testa
	glp_arc* arcp = G->v[i]->out;
	while(arcp != NULL){
		if(arcp->head->i == j){
			return 1;
		}
		arcp = arcp->t_next;
	}
	return 0;
}

e_data* get_e_data(glp_arc* e){
	return (e_data*)e->data;
} 

void set_arc_w(glp_arc* e, double d){
	get_e_data(e)->w = d;
	return;
}

double get_arc_w(glp_arc* e){
	return get_e_data(e)->w;
}

int custom_write_graph(glp_graph *G, const  char* filename){
	FILE* fp;
	int i,tail,head;
	double w;
	glp_arc* arcp;
	
	fp = fopen(filename, "w");
	
	fprintf(fp,"%d %d\n",G->nv,G->na);  // Scrive il numero di archi e di nodi
	
	for(i = 1; i <= G->nv; i++){
		//Per ogni nodo nel grafo
		arcp = G->v[i]->out; //lista di archi uscenti dal nodo corrente
		while(arcp != NULL){
			tail = arcp->tail->i;
			head = arcp->head->i;
			w = get_arc_w(arcp);
			
			fprintf(fp,"%d %d %lf\n",tail,head,w);

			arcp = arcp->t_next;
		}
	} 
	
	
	fclose(fp);
	return 0;
}



int custom_read_graph(glp_graph *G, const  char* filename){
	FILE* fp;
	int n,e,i,v1,v2;
	double w;
	glp_arc* arcp;
	char str[128];

	fp = fopen(filename, "r");
	
	// TODO erase del grafo in input (per sicurezza)
	// TODO controllo se FP==null
		
	// Istanziazione grafo
	glp_set_graph_name(G, "Grafo letto");
		
	fscanf(fp,"%d %d\n",&n,&e); // la prima riga contiene numero di nodi e archi, separati da uno spazio
	
	// Inserimento nodi
	for (i = glp_add_vertices(G, n) ; i <= n ; i++){
		strcpy(str,"");		
		itoa(i,str);
		glp_set_vertex_name(G, i, str);

	}

	// Inserimento archi
	for (i = 1; i <= e ; i++){		
		fscanf(fp,"%d %d %lf\n",&v1,&v2,&w); // le righe successive contengono gli archi nella notazione "coda testa peso"
		
		arcp = glp_add_arc(G,v1,v2);
		set_arc_w(arcp,w);
	}
	
	fclose(fp);
	return 0;
}

int custom_write_sol(glp_graph* G, glp_prob* lp, const char* filename){
	FILE* fp;
	int i;
	double z;
	char str_source[128];
	char* str_tail;
	char* str_head;
	char c;
	
	strcpy(str_source,"");
	fp = fopen(filename, "w");
	
	z = glp_get_obj_val(lp);	
	
	fprintf(fp,"%d %d %lf\n",G->nv,G->na,z);  // Scrive il numero di archi e di nodi
	
	//Formato: coda testa valore soluzione
	for (i = 0; i < glp_get_num_cols(lp); i++){
		strcpy(str_source, glp_get_col_name(lp, i+1));
		
		strtok(str_source, "_");//inizializza il tokenizzatore
		str_tail = strtok(NULL, "_");//estrae il primo _
		str_head = strtok(NULL, "_");//estrae il secondo _
		
		fprintf(fp,"%s %s %lf\n", str_tail, str_head, glp_get_col_prim(lp, i+1));
	}
	
	fclose(fp);
	return 0;
}

glp_graph* custom_create_graph(){
	return glp_create_graph(0, sizeof(e_data)); // pesato sugli archi
}

void custom_erase_graph(glp_graph* G){
	glp_erase_graph(G,0,sizeof(e_data));
}

void custom_delete_graph(glp_graph* G){
	glp_delete_graph(G);
}

glp_graph* random_graph_v2(int min_n, int max_n, int min_w, int max_w){
	glp_graph* G;
	int i,n,e,v1,v2,is_connected;
	int* degree_v;
	char str[128];
	glp_arc* arcp;
	double w;
	// Inizializzazione variabili
	strcpy(str, "");

	// Generazione della dimensione del grafo
	randomize();
	n = randomf(min_n,max_n); 
	e = randomf(n-1,(n*(n-1))/2);	// il grafo deve essere connesso quindi il min è n-1 nodi
					// cappi ed archi ripetuti sono proibiti, mentre archi tipo (x,y) e (y,x) sono permessi
					// ogni nodo ha quindi al più n-1 archi uscenti, dunque al più n*n-1 archi

	
	degree_v = malloc(sizeof(int)*(n+1)); //notazione GLPK like
	
	do{

		for (i = 1 ; i <= n ; i++) degree_v[i] = 0;
		
		// Creazione grafo
		G = custom_create_graph();
		glp_set_graph_name(G, "Grafo casuale");
	
		// Inserimento nodi
		for (i = glp_add_vertices(G, n) ; i <= n ; i++){
			strcpy(str,"");		
			itoa(i,str);
			glp_set_vertex_name(G, i, str);

		}
	
		//printf("n:%d e:%d\n",n,e);
	
	
		// Inserimento archi
		for (i = 1; i <= e ; i++){
			v1 = randomf(1,n);
			v2 = randomf(1,n);
		
		
			while(v1 == v2 || exists_arc(G,v1,v2) || exists_arc(G,v2,v1) ){  // proibisce cappio o ripetizione di arco		
				// calcola un nuovo arco casuale

				// Attenzione, se restano pochi archi inseribili in un grafo molto grande può richiedere tempo
				// 	Richede qualche secondo per generare grafi completi di circa 200 nodi

				v1 = randomf(1,n);
				v2 = randomf(1,n);
			}
		
			arcp = glp_add_arc(G,v1,v2);
			degree_v[v1]++;
			degree_v[v2]++;
			w = (double)randomf(min_w,max_w);
			set_arc_w(arcp,w);
			//printf("(%d,%d)\n",v1,v2);

		}
	
		//for (i = 1 ; i <= n ; i++)printf("deg(%d) = %d\n",i,degree_v[i]);
	
		is_connected = 1;
		for (i = 1 ; i <= n ; i++){
			if(degree_v[i]==0){
				is_connected = 0;
			}
		}
		
		if (!is_connected){
			custom_delete_graph(G);
			//printf("grafo cancellato\n");
		}
				
	}while(!is_connected);

	return G;
}

int get_node_degree(glp_graph* G,int i){
	glp_arc* arcp;
	int degree;
	
	degree = 0;
	
	arcp = G->v[i]->out;
	while(arcp != NULL){
		//printf("1F : %d,%d\n",arcp->tail->i,arcp->head->i);
		degree++;
		arcp = arcp->t_next;
	}
	
	arcp = G->v[i]->in;
	while(arcp != NULL){
		//printf("2F : %d,%d\n",arcp->tail->i,arcp->head->i);
		degree++;
		arcp = arcp->h_next;
	}
	
	return degree;
}

glp_graph* random_graph(int min_n, int max_n, int min_w, int max_w){	
	glp_graph* G;
	int i,n,e,v1,v2;
	char str[128];
	glp_arc* arcp;
	double w;
	// Inizializzazione variabili
	strcpy(str, "");

	// Generazione della dimensione del grafo
	randomize();
	n = randomf(min_n,max_n); 
	e = randomf(n-1,n*(n-1));	// il grafo deve essere connesso quindi il min è n-1 nodi
					// cappi ed archi ripetuti sono proibiti, mentre archi tipo (x,y) e (y,x) sono permessi
					// ogni nodo ha quindi al più n-1 archi uscenti, dunque al più n*n-1 archi

	// Creazione grafo
	G = custom_create_graph();
	glp_set_graph_name(G, "Grafo casuale");
	
	// Inserimento nodi
	for (i = glp_add_vertices(G, n) ; i <= n ; i++){
		strcpy(str,"");		
		itoa(i,str);
		glp_set_vertex_name(G, i, str);

	}

	// Inserimento archi per garantire la connessione
	for (i = 1 ; i <= n-1 ; i++){
		//sto connettendo il nodo i
		if(rand()%2 == 1){	//rendo casuale la direzione dell'arco che connette i
			// genero un arco (i,random)
			v1 = i;
			v2 = randomf(1,n);
			
			while(v1 == v2 || exists_arc(G,v1,v2) || exists_arc(G, v2, v1)){ // proibisce cappio o ripetizione di arco
				// calcolo un nuovo arco che garantisce la copertura del nodo corrente (con la stessa direzione)
				v2 = randomf(1,n);
			}
		}else{
			// genero un arco (random,i)
			v1 = randomf(1,n);
			v2 = i;
			while(v1 == v2 || exists_arc(G,v1,v2) || exists_arc(G, v2, v1)){  // proibisce cappio o ripetizione di arco
				// calcolo un nuovo arco che garantisce la copertura del nodo corrente (con la stessa direzione)
				v1 = randomf(1,n);
			}
			
		}
		
		
		arcp = glp_add_arc(G,v1,v2);
		w = (double)randomf(min_w,max_w);
		set_arc_w(arcp,w);

	}
	

	// Inserimento archi
	for (i = n; i <= e ; i++){
		v1 = randomf(1,n);
		v2 = randomf(1,n);
		
		
		while(v1 == v2 || exists_arc(G,v1,v2) ){  // proibisce cappio o ripetizione di arco		
			// calcola un nuovo arco casuale

			// Attenzione, se restano pochi archi inseribili in un grafo molto grande può richiedere tempo
			// 	Richede qualche secondo per generare grafi completi di circa 200 nodi

			v1 = randomf(1,n);
			v2 = randomf(1,n);
		}
		
		arcp = glp_add_arc(G,v1,v2);
		w = (double)randomf(min_w,max_w);
		set_arc_w(arcp,w);

	}

	return G;
}

int apply_on_edges(int(*pfun)(glp_arc*), glp_graph* G){
	int i,retval;
	glp_arc* arcp;

	for(i = 1; i <= G->nv; i++){
		//Per ogni nodo nel grafo
		arcp = G->v[i]->out; //lista di archi uscenti dal nodo corrente
		while(arcp != NULL){
			retval = pfun(arcp);
			if(retval != 0) return retval;
			arcp = arcp->t_next;
		}
	} 
	return 0;
}

int get_number_of_arcs(glp_graph *G) {
  return G->na;
}

int get_number_of_nodes(glp_graph *G) {
  return G->nv;
}
glp_arc* arc_iterator(glp_graph* G,int r){
	static glp_arc* arcp;
	static int i;

	glp_arc* retval;
	
	if(r == 1){
		i = 1;
		arcp = G->v[i]->out;
		return NULL;
	}
	
	
	while(i <= G->nv){
		if(arcp != NULL){
			retval = arcp;
			arcp = arcp->t_next;
			return retval;
		}else{
			i++;
			if(i <= G->nv)arcp = G->v[i]->out;
		}
	}
	
	return NULL;
}

void generate_arc_name(glp_arc* arcp,char* str){
	char strnum[10];
	strcpy(str,"x_");
	itoa(arcp->tail->i,strnum);
	strcat(str,strnum);
	strcat(str,"_");
	itoa(arcp->head->i,strnum);
	strcat(str,strnum);
	return;
}
